package 二叉树;

public class No222完全二叉树的节点个数 {

    /**
     * 给出一个完全二叉树，求出该树的节点个数。
     *
     * 说明：
     *
     * 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
     *
     * 示例:
     *
     * 输入:
     *     1
     *    / \
     *   2   3
     *  / \  /
     * 4  5 6
     * 输出: 6
     */

    //不讲武德解法(通用节点个数)
    public static int countNodesBad(TreeNode root) {
        if(root==null)
            return 0;
        int left=countNodesBad(root.left);
        int right=countNodesBad(root.right);
        return left+right+1;
    }

    /**
     * 思路,从一个节点开始,一个左子树一个右子树,然后判断两个子树左孩子的深度是否相等
     * 1.相等
     *      加上整合左子树(满的)的个数[(2^h-1)+root=2^h],则断层还在右子树,递归右子树
     * 2.不相等
     *      加上右子树(满的)的个数[(2^h-1)+root=2^h],则断层在左子树,递归左子树
     * 太厉害了,这样每个节点都会遍历到。
     */
    public static int countNodes(TreeNode root){
        if(root==null)
            return 0;
        /**
         * 都最左判断即可
         */
        int left=level(root.left);
        int right=level(root.right);

        if(left==right){
            //断层在右子树,加上左子树的个数和当前节点的个数
            return countNodes(root.right)+((int)Math.pow(2, left)-1)+1;
        }else{
            //断层在左子树,加上右子树的个数和当前节点的个数
            return countNodes(root.left)+((int)Math.pow(2, right)-1)+1;
        }
    }

    private static int level(TreeNode node){
        int deep=0;
        while (node!=null){
            node=node.left;
            deep++;
        }
        return deep;
    }

    public static void main(String[] args) {
        TreeNode nodeByArr = TreeNode.getNodeByArr(new Integer[]{1, 2, 3, 4, 5, 6});
        int i = countNodes(nodeByArr);
        System.out.println(i);
        //1 2 4
    }

}
